1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the design of storage structures used in data processing and data communication devices.
2. Background Information
FIG. 1 illustrates a prior art storage structure equipped to support random read and write of its storage locations. Storage structure 50 includes memory array 52 having a number of memory locations, write enable control signal pin 54, address input pins 56a-56b, and data in and out pins 58a-58b. By setting write enable control signal 54 to denote a xe2x80x9cwritexe2x80x9d operation, and applying the appropriate address information to address input pins 56a, write data applied to data in pins 58a may be written into any memory location of memory array 52. Similarly, by applying the appropriate address information to address input pins 56b, previously written data stored in any memory location of memory array 52 may be retrieved and made available at data out pins 58b. While storage structure is designed to facilitate random read/write, of course a host process may elect to write to and read from its storage locations sequentially, by shouldering the responsibility of ensuring that all successive write/read addresses issued are sequential in nature. [The term host process, as used herein in this application, in intended to include hardware and/or software.]
FIG. 2 illustrates a prior art first in, first out storage structure (FIFO) designed to support sequential write and read, without requiring a host process to shoulder the responsibility of ensuring the successive write/read addresses issued are sequential in nature. Storage structure 60 includes dual port memory array 62 having a number of memory locations, write counter 64, read counter 66 and full/empty logic 68, coupled to each other as shown. Write data may be sequentially written into memory locations of memory array 62 by applying a write signal to increment write counter 64, whose output is applied to the write address inputs of memory array 62. Likewise, read data may be sequentially read from memory locations of memory array 62 by applying a read signal to increment read counter 66, whose output is applied to the read address inputs of memory array 62. A host process need not be concerned with maintaining the sequential nature of the write/read addresses. By monitoring the output of write and read counters 64 and 66, full/empty logic 68 is able to set a xe2x80x9cfullxe2x80x9d control signal to xe2x80x9ctruexe2x80x9d to inform a host process that RAM array 62 is full (accordingly, should not be further written into) and set an xe2x80x9cemptyxe2x80x9d control signal to xe2x80x9cfalsexe2x80x9d to inform the host process that RAM array 62 is non-empty (accordingly, should be read to process the written data).
In a number of applications, while the basic write and read operations are fundamentally sequential in nature, nevertheless it may be desirable to be able to perform random re-reads in addition to the fundamental sequential write/read operations. An example of such applications is one where data are sequentially queued, and multiple sets of the queued data are to be sequentially examined and processed concurrently in a pipelined multi-stage fashion. To facilitate the multi-set pipelined multi-stage fashion of processing, earlier queued data must be xe2x80x9cpopped offxe2x80x9d to make the later queued data visible, and yet all xe2x80x9cpopped offxe2x80x9d data must remain available until all stages of processing are completed. One obvious approach, if a storage structure similar to the one illustrated in FIG. 2 is continued to be used, is to provide additional hardware to store the xe2x80x9cpopped offxe2x80x9d data, making the stored data available until all processing is completed. Another approach is to revert to the use of a storage structure similar to the one illustrated by FIG. 1. Under such approach, the xe2x80x9cpopped offxe2x80x9d data will still be re-accessible, until they are discarded. However, as alluded to earlier, the burden of maintaining the sequential nature of the fundamental writes and reads will be reverted back to the host process. Neither approach is desirable.
A specific application where such situations occur is in networking switch and router applications. Network switches/routers receive continuous streams of packets, and the included IP or MAC addresses are queued and examined to determine where the packets should be switched or routed. The determination typically involves data look ups. For performance reasons, it is desirable to be able to perform the look up for multiples of these IP/MAC addresses concurrently in a pipelined multi-stage fashion. However, as alluded to earlier, it is desirable if the concurrent processing can be made possible without having to resort to the use of RAM or registers to xe2x80x9cqueuexe2x80x9d up the IP/MAC addresses (and shifting the burden of maintaining the sequential nature of the fundamental writes and reads to the host process) nor having to pay the price of replicating the hardware required to carry the xe2x80x9ccontextxe2x80x9d information of each IP/MAC address being concurrently processed.
Thus, a novel storage structure that can better accommodate this type of processing is desired.
The present invention includes a novel FIFO storage structure. The FIFO storage structure is provided with a RAM array including a number of memory locations, and control circuitry coupled to the RAM array. The control circuitry facilitates sequential write and read accesses of the memory locations, as well as non-sequential re-read of memory locations previously read in sequence. In particular, the control circuitry includes circuit elements for facilitating variably deferred release and reclaiming of sequentially read in-use ones of the memory locations.